GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Teilgraph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Teilgraph</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Begriff Teilgraph beschreibt in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> eine Beziehung zwischen zwei <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>. Ein Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> ist Teilgraph des Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, wenn alle Knoten und Kanten von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> auch in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> enthalten sind.

Anders gesagt: Ein Teilgraph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> entsteht aus einem Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, indem einige Knoten und Kanten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> entfernt werden. Dabei müssen beim Entfernen eines Knotens auch alle <a href="Nachbarschaft_(Graphentheorie)" title="Nachbarschaft (Graphentheorie)">inzidenten</a> Kanten mit entfernt werden.

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Ein Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(V_{1},E_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=(V_{1},E_{1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce54faeead4cd211047907a335458e7dc8306daf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V_{1},E_{1})}" loading="lazy"> heißt Teilgraph oder Subgraph von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(V_{2},E_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(V_{2},E_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2e832bb526bf16909e2e39f7332a036103557d1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=(V_{2},E_{2})}" loading="lazy">, wenn seine Knotenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> <a href="Teilmenge" title="Teilmenge">Teilmenge</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ceaa689a894f5020a7b46177d201cbce2d41122b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{2}}" loading="lazy"> und seine Kantenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ac42446bcd2cbb76ec8fe2895635d328da22e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{1}}" loading="lazy"> Teilmenge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e6ee346e54f38302f47b5cf3016d8718f2040c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{2}}" loading="lazy"> ist,

also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}\subseteq V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}\subseteq V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af4c6b1fc61ad08b0ac133487c568dd62c1303fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.917ex; height:2.509ex;" alt="{\displaystyle V_{1}\subseteq V_{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}\subseteq E_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}\subseteq E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/28a495f49a6102e26f524e9a03f85abd697c354c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.637ex; height:2.509ex;" alt="{\displaystyle E_{1}\subseteq E_{2}}" loading="lazy"> gilt.

Umgekehrt heißt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> dann Supergraph oder Obergraph von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">.

Bei einem <a href="Knotengewichteter_Graph" title="Knotengewichteter Graph">knotengewichteten</a> bzw. <a href="Kantengewichteter_Graph" title="Kantengewichteter Graph">kantengewichteten</a> Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> wird von einem Teilgraphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> zudem verlangt, dass die Gewichtsfunktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3755e3e04ec295992b2b5331655ef83a500a05c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.163ex; height:2.009ex;" alt="{\displaystyle g_{1}}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> kompatibel zu der Gewichtsfunktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f0261c34f2ad1e1b5317708b7f98ae13ee70ff1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.163ex; height:2.009ex;" alt="{\displaystyle g_{2}}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> sein muss, d. h. für jeden Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1e04b2c8f6226f1aa51ebc4f1b429bfbeff793e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.378ex; height:2.509ex;" alt="{\displaystyle v\in V_{1}}" loading="lazy"> gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}(v)=g_{2}(v)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}(v)=g_{2}(v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e56382e74e0216a41cc75f69de7bbbd8170ff06e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.299ex; height:2.843ex;" alt="{\displaystyle g_{1}(v)=g_{2}(v)}" loading="lazy"> bzw. für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/19f7cd88c3267329b35b5fe4a9187d1fc6644e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.694ex; height:2.509ex;" alt="{\displaystyle e\in E_{1}}" loading="lazy"> gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}(e)=g_{2}(e)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}(e)=g_{2}(e)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1499d6156ddde9a8491bdd7539e32024326acd24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.211ex; height:2.843ex;" alt="{\displaystyle g_{1}(e)=g_{2}(e)}" loading="lazy">.

Gilt für einen Teilgraphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> zusätzlich, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ac42446bcd2cbb76ec8fe2895635d328da22e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{1}}" loading="lazy"> alle Kanten zwischen den Knoten in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> enthält, die auch in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e6ee346e54f38302f47b5cf3016d8718f2040c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle E_{2}}" loading="lazy"> vorhanden sind, so bezeichnet man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> als den durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/adfdbc929f16cb00bb43289c223651b41f7b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle V_{1}}" loading="lazy"> induzierten Teilgraph oder als Untergraph von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> und notiert diesen auch mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}[V_{1}]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}[V_{1}]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ef703db859d5bac3ed835b4c1aef8d57e33d7c11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.584ex; height:2.843ex;" alt="{\displaystyle G_{2}[V_{1}]}" loading="lazy">.

Ein induzierter Teilgraph ist immer eindeutig durch den Obergraphen und die gewählte Knotenmenge bestimmt.

Für eine Knotenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W\subseteq V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W\subseteq V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7d05af9d62859741b09533bd82087feb0a9b298.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.321ex; height:2.343ex;" alt="{\displaystyle W\subseteq V}" loading="lazy"> bezeichnet man mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G\setminus W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G\setminus W}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b5ff84436e39dbf2788973dfb53630c2c2acd79d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.457ex; height:2.843ex;" alt="{\displaystyle G\setminus W}" loading="lazy"> den induzierten Teilgraphen,

der aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> durch Weglassen der Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"> und aller mit diesen Knoten inzidenten Kanten entsteht, also

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G\setminus W=G[V\setminus W]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e13c0af0aca25705b098b14e52d9d711e8ebf137.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.093ex; height:2.843ex;" alt="{\displaystyle G\setminus W=G[V\setminus W]}" loading="lazy">.

Ein Teilgraph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(V,E_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=(V,E_{1})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9238b055fe5768c0544b4a053ce609e090e9076.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.379ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V,E_{1})}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(V,E_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(V,E_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f975382fd0707722fdcc38355437487681e70d82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.379ex; height:2.843ex;" alt="{\displaystyle G_{2}=(V,E_{2})}" loading="lazy">, der alle Knoten seines Obergraphen enthält, wird aufspannender Teilgraph oder Faktor genannt.

Diese Bezeichnungen sind in der Literatur nicht einheitlich. Im unten angegebenen Lehrbuch von <a href="Klaus_Wagner_(Mathematiker)" title="Klaus Wagner (Mathematiker)">Klaus Wagner</a><a href="#cite_note-1">[1]</a> werden die Begriffe Teilgraph und Untergraph so verwendet, wie hier beschrieben. Im Lehrbuch von <a href="Claude_Berge" title="Claude Berge">Claude Berge</a><a href="#cite_note-2">[2]</a> dagegen bedeutet Teilgraph zusätzlich, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}=V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}=V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42fa39fdae54eeb8df60303dd39905f1871df9ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.917ex; height:2.509ex;" alt="{\displaystyle V_{1}=V_{2}}" loading="lazy"> ist (also ein aufspannender Teilgraph vorliegt), und Untergraph, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}\subset V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1}\subset V_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/975e9cd94faab4fa416ee385cc42c0dd19d2be9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.917ex; height:2.509ex;" alt="{\displaystyle V_{1}\subset V_{2}}" loading="lazy"> und jede Kante aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">, die zwei Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> verbindet, auch eine Kante in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> ist (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> also ein induzierter Teilgraph ist), der allgemeine Fall heißt dann dort Teil-Untergraph. Es empfiehlt sich daher, bei jedem Autor, die verwendete Definition zu prüfen.

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

In der folgenden Abbildung sind die Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d68b13104a6f81e902fca48f10a1531b3e592938.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}" loading="lazy"> Teilgraphen von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, aber nur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d68b13104a6f81e902fca48f10a1531b3e592938.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}" loading="lazy"> sind induzierte Teilgraphen. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d68b13104a6f81e902fca48f10a1531b3e592938.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}" loading="lazy"> entsteht dabei aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> durch Weglassen der Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,3,7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,3,7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17ecd577ac35fd2aa8009c1c2cb0e805f6dda24e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.555ex; height:2.509ex;" alt="{\displaystyle 1,3,7}" loading="lazy"> und ihrer inzidenten Kanten, also ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}=G\setminus \{1,3,7\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{3}=G\setminus \{1,3,7\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4a9cd0b199b25d5502e4f417a5039cde23220974.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.881ex; height:2.843ex;" alt="{\displaystyle G_{3}=G\setminus \{1,3,7\}}" loading="lazy">. Gleichzeitig ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d68b13104a6f81e902fca48f10a1531b3e592938.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}" loading="lazy"> auch ein induzierter Teilgraph von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Unterteilungsgraph" title="Unterteilungsgraph">Unterteilungsgraph</a></li>

<li><a href="Minor_(Graphentheorie)" title="Minor (Graphentheorie)">Minor (Graphentheorie)</a></li>

<li><a href="Spannbaum" title="Spannbaum">Spannbaum</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Reinhard Diestel: Graphentheorie. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5. (354 Seiten, <a rel="nofollow" class="external text" href="https://diestel-graph-theory.com/">online</a>)</li>

<li>Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (<a rel="nofollow" class="external text" href="https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf">neuere Online-Version „Graphen an allen Ecken und Kanten“</a>; PDF; 3,51 MB)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Klaus Wagner: Graphentheorie, BI-Hochschultaschenbücher (1969), Band 248, Kap. I, §3, Definition 4

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Claude Berge: Programme, Spiele, Transportnetze, Teubner-Verlag 1969, Zeiter Teil, Kap. I, Absatz 1, Seite 121

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-09-12" href="https://de.wikipedia.org/wiki/?title=Teilgraph&oldid=248544625">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>